home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / graphics / font3d10.zip / geometry.cpp < prev    next >
C/C++ Source or Header  |  1994-09-15  |  19KB  |  560 lines
  1. //=================================================================================================
  2. //   Geometry.CPP
  3. //-------------------------------------------------------------------------------------------------
  4. //
  5. //   Copyright (c) 1994 by Todd A. Prater
  6. //   All rights reserved.
  7. //
  8. //=================================================================================================
  9.  
  10. #include <math.h>
  11. #include <stddef.h>
  12. #include <stdio.h>
  13. #include <iostream.h>
  14. #include "Geometry.H"
  15. #include "List.H"
  16. #include "Config.H"
  17.  
  18. #define BIG  1.0e30
  19. #define ERR_OUTOFMEMORY 2
  20. #define ERR_NOPOLYFOUND 1
  21. #define NOERROR         0
  22.  
  23.  
  24.  
  25.  
  26. //===========================================================================================================
  27. //-----------------------------------------------------------------------------------------------------------
  28. //===========================================================================================================
  29.  
  30.  
  31. ostream& operator << (ostream& s, const TRIANGLE& t)
  32. {
  33.     s<<"triangle {"<<t.v1<<","<<t.v2<<","<<t.v3<<"}";
  34.     return s;
  35. }
  36.  
  37.  
  38.  
  39. //===========================================================================================================
  40. //  TRIANGLE::Output                                                                               (PUBLIC)
  41. //-----------------------------------------------------------------------------------------------------------
  42. //===========================================================================================================
  43.  
  44.  
  45. void TRIANGLE::Output(ostream& s, ULONG format)
  46. {
  47.     switch(format)
  48.     {
  49.       case RAW:
  50.           s<<v1.x<<" "<<v1.y<<" "<<v1.z<<" "
  51.            <<v2.x<<" "<<v2.y<<" "<<v2.z<<" "
  52.            <<v3.x<<" "<<v3.y<<" "<<v3.z;
  53.           break;
  54.       case POV_FLAT :
  55.           s<<"triangle {"<<v1<<","<<v2<<","<<v3<<"}";
  56.           break;
  57.       case POV_SMOOTH:
  58.           s<<"smooth_triangle {"<<v1<<","<<n1<<","
  59.                                 <<v2<<","<<n2<<","
  60.                                 <<v3<<","<<n3<<"}";
  61.           break;
  62.     }
  63. }
  64.  
  65.  
  66.  
  67. //===========================================================================================================
  68. //-----------------------------------------------------------------------------------------------------------
  69. //===========================================================================================================
  70.  
  71.  
  72. ostream& operator << (ostream& s, const POLYGON& p)
  73. {
  74.     if (p.numpoints==0)
  75.         s<<"EMPTY POLYGON\n";
  76.     else
  77.     {
  78.         s<<"POLYGON with "<<p.numpoints<<" sides:\n";
  79.         for (int i=0;i<p.numpoints;i++)
  80.             s<<"   "<<p.pointlist[i]<<"\n";
  81.     }
  82.  
  83.     return s;
  84. }
  85.  
  86.  
  87.  
  88. //===========================================================================================================
  89. //  POLYGON                                                                                        (PUBLIC)
  90. //-----------------------------------------------------------------------------------------------------------
  91. //  These are the constructors for the POLYGON class.  The first creates a POLYGON with no vertices, the  
  92. //  second creates a POLYGON given an array of n points, and the third is a copy constructor.
  93. //===========================================================================================================
  94.  
  95.  
  96. POLYGON::POLYGON(void)
  97. {
  98.     numpoints   = 0;              
  99.     pointlist   = NULL;
  100.     orientation = CLOCKWISE;
  101. }
  102.                                   
  103. POLYGON::POLYGON(INT n, VECTOR* p)
  104. {
  105.     numpoints   = n;
  106.     pointlist   = p;
  107.     orientation = findOrientation();
  108. }
  109.  
  110. POLYGON::POLYGON(POLYGON& P)
  111. {
  112.     numpoints   = P.numpoints;
  113.     pointlist   = new VECTOR[numpoints];
  114.     for (int i=0;i<numpoints;i++)
  115.        pointlist[i]=P.pointlist[i];
  116.     orientation = P.orientation;
  117. }
  118.                 
  119.  
  120.  
  121. //===========================================================================================================
  122. //  POLYGON::findOrientation                                                                       (PRIVATE)
  123. //-----------------------------------------------------------------------------------------------------------
  124. //  This function calculates the orientation of a POLYGON.                                                
  125. //===========================================================================================================
  126.  
  127.  
  128. ORIENTATIONTYPE POLYGON::findOrientation(void)
  129. {
  130.     DOUBLE area;
  131.     INT    i;
  132.  
  133.     area =  pointlist[numpoints-1].x * pointlist[0].y
  134.           - pointlist[0].x * pointlist[numpoints-1].y;
  135.  
  136.     for (i=0;i<numpoints-1;i++)
  137.         area +=  pointlist[i].x * pointlist[i+1].y
  138.                - pointlist[i+1].x * pointlist[i].y;
  139.  
  140.     if (area >= 0.0)
  141.         return COUNTER_CLOCKWISE;
  142.     else
  143.         return CLOCKWISE;
  144.  
  145. }
  146.  
  147.  
  148.  
  149. //===========================================================================================================
  150. //  POLYGON::findDeterminant                                                                       (PRIVATE)
  151. //-----------------------------------------------------------------------------------------------------------
  152. //  Finds the orientation of the triangle formed by connecting the POLYGON's p1, p2, and p3 vertices.     
  153. //===========================================================================================================
  154.  
  155.  
  156. ORIENTATIONTYPE POLYGON::findDeterminant(INT p1, INT p2, INT p3)
  157. {
  158.     DOUBLE determinant;
  159.  
  160.     determinant = (pointlist[p2].x-pointlist[p1].x)
  161.                  *(pointlist[p3].y-pointlist[p1].y)
  162.                  -(pointlist[p3].x-pointlist[p1].x)
  163.                  *(pointlist[p2].y-pointlist[p1].y);
  164.  
  165.     if (determinant >= 0.0)
  166.         return COUNTER_CLOCKWISE;
  167.     else
  168.         return CLOCKWISE;
  169.  
  170. }
  171.  
  172.  
  173.  
  174. //===========================================================================================================
  175. //  POLYGON::noneInside                                                                            (PRIVATE)
  176. //-----------------------------------------------------------------------------------------------------------
  177. //  Returns 'FALSE' if any of the POLYGON's vertices in 'vlist' are inside the triangle formed by connecting
  178. //  the vertices p1, p2, and p3.  'n' is the number of vertices in 'vlist'.  Returns 'TRUE' if no vertices
  179. //  are inside that triangle.
  180. //===========================================================================================================
  181.  
  182.         
  183. BOOLEAN POLYGON::noneInside(INT p1, INT p2, INT p3, INT n, INT* vlist)
  184. {
  185.     INT i,p;
  186.  
  187.     for(i=0;i<n;i++)
  188.     {
  189.         p=vlist[i];
  190.         if((p==p1)||(p==p2)||(p==p3)) continue;
  191.         if (   (findDeterminant(p2,p1,p)==orientation)
  192.             || (findDeterminant(p1,p3,p)==orientation)
  193.             || (findDeterminant(p3,p2,p)==orientation))  continue;
  194.         else
  195.         {
  196.            if (  (pointlist[p].x==pointlist[p1].x && pointlist[p].y==pointlist[p1].y)
  197.                ||(pointlist[p].x==pointlist[p2].x && pointlist[p].y==pointlist[p2].y)
  198.                ||(pointlist[p].x==pointlist[p3].x && pointlist[p].y==pointlist[p3].y))
  199.               continue;
  200.            else
  201.               return FALSE;
  202.         }
  203.     }
  204.     return TRUE;
  205. }
  206.  
  207.  
  208.  
  209. //===========================================================================================================
  210. //  POLYGON::Triangulate                                                                           (PUBLIC) 
  211. //-----------------------------------------------------------------------------------------------------------
  212. //  Slices the POLYGON up into a list of triangles.  The POLYGON must be non-intersecting.  This is done by 
  213. //  checking each vertex to see whether or not it can be 'chopped off'.  If so, that vertex is removed, and
  214. //  the process is repeated until there are only three vertices left (only one triangle left).
  215. //  Returns the following values upon completion:
  216. //
  217. //       ERR_NOPOLYFOUND .......... If there were more than three vertices left, but none of them could
  218. //                                  be 'chopped off'.  This usually happens if the polygon intersects
  219. //                                  itself.
  220. //
  221. //       NOERROR .................. If the polygon was successfully triangulated.
  222. //
  223. //===========================================================================================================
  224.  
  225.  
  226. INT POLYGON::Triangulate(LIST<TRIANGLE>& trilist)
  227. {
  228.     TRIANGLE*         current_triangle;
  229.     INT               triangle_count;
  230.     INT               previous;
  231.     INT               current;
  232.     INT               next;
  233.     INT*              rvl;
  234.     INT               vertex_count;
  235.     DOUBLE            current_distance;
  236.     ORIENTATIONTYPE   current_determinant;
  237.     BOOLEAN           current_position;
  238.     INT               i;
  239.     VECTOR            p1,p2,p3;
  240.     BOOLEAN           done;
  241.     VECTOR            n1(0,0,1);
  242.     VECTOR            n2(0,0,1);
  243.     VECTOR            n3(0,0,1);
  244.  
  245.     rvl = new INT[numpoints];
  246.     for (i=0;i<numpoints;i++) 
  247.         rvl[i]=i;
  248.  
  249.     vertex_count=numpoints;
  250.     while (vertex_count>3)
  251.     {
  252.         done=FALSE;
  253.         previous=vertex_count-1;
  254.         current=0;
  255.         next=1;
  256.         while (current<vertex_count && !done)
  257.         {
  258.             previous = current-1;
  259.             next     = current+1;
  260.  
  261.             if (current==0)
  262.                 previous=vertex_count-1;
  263.             else if (current==vertex_count-1)
  264.                 next=0;
  265.  
  266.             current_determinant = findDeterminant(rvl[previous],
  267.                                                rvl[current],
  268.                                                rvl[next]);
  269.  
  270.             current_position = noneInside(rvl[previous] ,
  271.                                        rvl[current]  ,
  272.                                        rvl[next]     ,
  273.                                        vertex_count  ,
  274.                                        rvl          );
  275.  
  276.             if (   (current_determinant==orientation)
  277.                 && (current_position==TRUE))
  278.             {
  279.                 done=TRUE;
  280.             }
  281.             else
  282.             {
  283.                 current++;
  284.             }
  285.         }
  286.  
  287.         if (!done)
  288.         {
  289.            cout<<"ERROR:  No Polygon Found."<<endl;
  290.            return ERR_NOPOLYFOUND;
  291.         }
  292.  
  293.         p1=VECTOR(pointlist[rvl[previous]]);
  294.         p2=VECTOR(pointlist[rvl[current]]);
  295.         p3=VECTOR(pointlist[rvl[next]]);
  296.  
  297.         current_triangle = new TRIANGLE(p1,p2,p3,n1,n2,n3);
  298.         trilist.Add(current_triangle);
  299.  
  300.         vertex_count-=1;
  301.         for (i=current;i<vertex_count;i++) rvl[i]=rvl[i+1];
  302.  
  303.     }
  304.  
  305.     p1=VECTOR(pointlist[rvl[0]]);
  306.     p2=VECTOR(pointlist[rvl[1]]);
  307.     p3=VECTOR(pointlist[rvl[2]]);
  308.  
  309.     current_triangle = new TRIANGLE(p1,p2,p3);
  310.     trilist.Add(current_triangle);
  311.  
  312.     delete rvl;
  313.  
  314.     return NOERROR;
  315.  
  316. }
  317.  
  318.  
  319.  
  320.  
  321.  
  322. //===========================================================================================================
  323. //  POLYGON::Combine                                                                               (PUBLIC) 
  324. //-----------------------------------------------------------------------------------------------------------
  325. //===========================================================================================================
  326.  
  327.  
  328. void POLYGON::Combine(POLYGON& p)
  329. {
  330.    INT    i,ni,j;
  331.    DOUBLE min_dist;
  332.    INT    min_i=0;
  333.    INT    min_j=0;
  334.    VECTOR* newpl;
  335.    newpl = new VECTOR[numpoints+p.numpoints+2];
  336.  
  337.  
  338.    min_dist = BIG;
  339.    for (i=0;i<numpoints;i++)
  340.       for (j=0;j<p.numpoints;j++)
  341.          if (dist(pointlist[i],p.pointlist[j])<min_dist)
  342.          {
  343.             min_dist = dist(pointlist[i],p.pointlist[j]);
  344.             min_i    = i;
  345.             min_j    = j;
  346.          }
  347.  
  348.    ni=0;
  349.  
  350.    for(i=0     ; i<=min_i      ;i++)  { newpl[ni]=pointlist[i];   ni++; }
  351.    for(i=min_j ; i<p.numpoints ;i++)  { newpl[ni]=p.pointlist[i]; ni++; }
  352.    for(i=0     ; i<=min_j      ;i++)  { newpl[ni]=p.pointlist[i]; ni++; }
  353.    for(i=min_i ; i<numpoints   ;i++)  { newpl[ni]=pointlist[i];   ni++; }
  354.  
  355.    numpoints = ni;
  356.    delete pointlist;
  357.    pointlist = newpl;
  358.  
  359. }
  360.  
  361.  
  362. //===========================================================================================================
  363. //  POLYGON::isInside                                                                              (PUBLIC)
  364. //-----------------------------------------------------------------------------------------------------------
  365. //===========================================================================================================
  366.  
  367.  
  368. int POLYGON::isInside(POLYGON& p)
  369. {
  370.    INT i;
  371.    DOUBLE max_inside_x = -BIG;  DOUBLE max_outside_x = -BIG;
  372.    DOUBLE max_inside_y = -BIG;  DOUBLE max_outside_y = -BIG;
  373.    DOUBLE min_inside_x =  BIG;  DOUBLE min_outside_x =  BIG;
  374.    DOUBLE min_inside_y =  BIG;  DOUBLE min_outside_y =  BIG;
  375.  
  376.    for (i=0;i<p.numpoints;i++)
  377.    {
  378.       if (p.pointlist[i].x > max_outside_x) max_outside_x = p.pointlist[i].x;
  379.       if (p.pointlist[i].y > max_outside_y) max_outside_y = p.pointlist[i].y;
  380.       if (p.pointlist[i].x < min_outside_x) min_outside_x = p.pointlist[i].x;
  381.       if (p.pointlist[i].y < min_outside_y) min_outside_y = p.pointlist[i].y;
  382.    }
  383.  
  384.    for (i=0;i<numpoints;i++)
  385.    {
  386.       if (pointlist[i].x > max_inside_x) max_inside_x = pointlist[i].x;
  387.       if (pointlist[i].y > max_inside_y) max_inside_y = pointlist[i].y;
  388.       if (pointlist[i].x < min_inside_x) min_inside_x = pointlist[i].x;
  389.       if (pointlist[i].y < min_inside_y) min_inside_y = pointlist[i].y;
  390.    }
  391.  
  392.    if (   (max_outside_x < max_inside_x) || (max_outside_y < max_inside_y)
  393.        || (min_outside_x > min_inside_x) || (min_outside_y > min_inside_y) ) 
  394.       return 0;
  395.    else
  396.       return 1;
  397.  
  398. }
  399.  
  400.  
  401.  
  402. //===========================================================================================================
  403. //  POLYGON::Encloses                                                                              (PUBLIC)
  404. //-----------------------------------------------------------------------------------------------------------
  405. //===========================================================================================================
  406.  
  407.  
  408. int POLYGON::Encloses(POLYGON& p)
  409. {
  410.    INT i;
  411.    DOUBLE max_inside_x = -BIG;  DOUBLE max_outside_x = -BIG;
  412.    DOUBLE max_inside_y = -BIG;  DOUBLE max_outside_y = -BIG;
  413.    DOUBLE min_inside_x =  BIG;  DOUBLE min_outside_x =  BIG;
  414.    DOUBLE min_inside_y =  BIG;  DOUBLE min_outside_y =  BIG;
  415.  
  416.    for (i=0;i<p.numpoints;i++)
  417.    {
  418.       if (pointlist[i].x > max_outside_x) max_outside_x = pointlist[i].x;
  419.       if (pointlist[i].y > max_outside_y) max_outside_y = pointlist[i].y;
  420.       if (pointlist[i].x < min_outside_x) min_outside_x = pointlist[i].x;
  421.       if (pointlist[i].y < min_outside_y) min_outside_y = pointlist[i].y;
  422.    }
  423.  
  424.    for (i=0;i<numpoints;i++)
  425.    {
  426.       if (p.pointlist[i].x > max_inside_x) max_inside_x = p.pointlist[i].x;
  427.       if (p.pointlist[i].y > max_inside_y) max_inside_y = p.pointlist[i].y;
  428.       if (p.pointlist[i].x < min_inside_x) min_inside_x = p.pointlist[i].x;
  429.       if (p.pointlist[i].y < min_inside_y) min_inside_y = p.pointlist[i].y;
  430.    }
  431.  
  432.    if (   (max_outside_x < max_inside_x) || (max_outside_y < max_inside_y)
  433.        || (min_outside_x > min_inside_x) || (min_outside_y > min_inside_y) )
  434.       return 0;
  435.    else
  436.       return 1;
  437.  
  438. }
  439.  
  440.  
  441.  
  442. //===========================================================================================================
  443. //  POLYGON::Shrink                                                                                (PUBLIC)
  444. //-----------------------------------------------------------------------------------------------------------
  445. //===========================================================================================================
  446.  
  447.  
  448. void POLYGON::Shrink(POLYGON& newPoly, DOUBLE shrinkFactor)
  449. {
  450.  
  451.    INT i;
  452.    VECTOR current,previous,next;
  453.    VECTOR toPrevious,toNext,inPrevious,inNext;
  454.    VECTOR inward;
  455.    DOUBLE angle;
  456.    VECTOR zDir(0,0,1);
  457.  
  458.    if (newPoly.numpoints>0)
  459.    {
  460.       delete newPoly.pointlist;
  461.       newPoly.numpoints = 0;
  462.    }
  463.  
  464.    newPoly.pointlist = new VECTOR[numpoints];
  465.    newPoly.numpoints = numpoints;
  466.  
  467.    previous = pointlist[numpoints-1];
  468.    current = pointlist[0];
  469.    next = pointlist[1];
  470.  
  471.    toPrevious = ~(previous-current);
  472.    toNext     = ~(next-current);
  473.  
  474.       inPrevious = zDir^toPrevious;
  475.       inNext     = toNext^zDir;
  476.  
  477.    angle  = acos(inPrevious%inNext);
  478.    inward = ~(inPrevious+inNext)*shrinkFactor;
  479.  
  480.  
  481.    newPoly.pointlist[0]=current+inward;
  482.  
  483.  
  484.    previous = pointlist[numpoints-2];
  485.    current = pointlist[numpoints-1];
  486.    next = pointlist[0];
  487.  
  488.    toPrevious = ~(previous-current);
  489.    toNext     = ~(next-current);
  490.  
  491.       inPrevious = zDir^toPrevious;
  492.       inNext     = toNext^zDir;
  493.  
  494.    angle  = acos(inPrevious%inNext);
  495.    inward = ~(inPrevious+inNext)*shrinkFactor;
  496.  
  497.  
  498.    newPoly.pointlist[numpoints-1]=current+inward;
  499.  
  500.  
  501.    for (i=1;i<numpoints-1;i++)
  502.    {
  503.       previous = pointlist[i-1];
  504.       current = pointlist[i];
  505.       next = pointlist[i+1];
  506.  
  507.       toPrevious = ~(previous-current);
  508.       toNext     = ~(next-current);
  509.  
  510.          inPrevious = zDir^toPrevious;
  511.          inNext     = toNext^zDir;
  512.  
  513.       angle  = acos(inPrevious%inNext);
  514.       inward = ~(inPrevious+inNext)*shrinkFactor;
  515.  
  516.  
  517.       newPoly.pointlist[i]=current+inward;
  518.  
  519.    }
  520.  
  521. }
  522.  
  523.  
  524.  
  525. //===========================================================================================================
  526. //  POLYGON::SetDepth                                                                              (PUBLIC)
  527. //-----------------------------------------------------------------------------------------------------------
  528. //===========================================================================================================
  529.  
  530.  
  531. void POLYGON::SetDepth(DOUBLE depth)
  532. {
  533.    for (INT i=0;i<numpoints;i++)
  534.       pointlist[i].z = depth;
  535. }
  536.  
  537.  
  538.  
  539. //===========================================================================================================
  540. //  ApproximateQuadraticSpline                                                                     (PUBLIC) 
  541. //-----------------------------------------------------------------------------------------------------------
  542. //===========================================================================================================
  543.  
  544.  
  545. VECTOR ApproximateQuadraticSpline(VECTOR cp1, VECTOR cp2, VECTOR cp3, DOUBLE t)
  546. {
  547.    DOUBLE i1 = (1-t)*(1-t);
  548.    DOUBLE i2 = 2*t*(1-t);
  549.    DOUBLE i3 = t*t;
  550.  
  551.    DOUBLE tx = i1*cp1.x + i2*cp2.x + i3*cp3.x;
  552.    DOUBLE ty = i1*cp1.y + i2*cp2.y + i3*cp3.y;
  553.    DOUBLE tz = cp1.z;
  554.  
  555.    return VECTOR(tx,ty,tz);
  556. }
  557.  
  558.  
  559.  
  560.